/**
* @version:1.0
* @author kevinnan.org.cn  2018212114@mail.hfut.edu.cn
* @date 2020/7/16
* @Content:常用排序算法实现
*/

#include "Sort.h"

Sort::Sort(){
	srand((unsigned)time(NULL)); 
	int a = 0, b = 100000;
	for(int i = 0; i < 5000; i++){
		array.push_back((rand() % (b-a))+ a);
	}
	cout<<"排序前:"<<endl;
	//DisplayArray(array);
}


void Sort::DisplayArray(const std::vector<int>& v){
	for(auto iter = v.begin(); iter != v.end(); iter++)
		cout<<*iter<<"\t";
	cout<<endl;
}


void Sort::BubbleSort(){
	//　新初始化一个数组，不要改变原数组的值．
	std::vector<int> array_copy = array;

	auto start = system_clock::now();

	for(int i = 0; i < array_copy.size(); i++){
		for(int j = 0; j < array_copy.size() - 1; j++){
			if(array_copy[j] > array_copy[j+1])
				swap(array_copy[j], array_copy[j+1]);
		}
	}

	auto end   = system_clock::now();
	auto duration = duration_cast<microseconds>(end - start);

	cout<<"冒泡排序后:"<<endl;
	//DisplayArray(array_copy);

	

	cout<<"花费了" 
     	<<double(duration.count()) * microseconds::period::num / microseconds::period::den 
     	<<"秒"<<endl;
}


void Sort::OptimizeBubbleSort(){
	//　新初始化一个数组，不要改变原数组的值．
	std::vector<int> array_copy = array;

	auto start = system_clock::now();

	bool is_change = false;
	for(int i = 0; i < array_copy.size(); i++){
		for(int j = 0; j < array_copy.size() - 1; j++){
			if(array_copy[j] > array_copy[j+1]){
				is_change = true;
				swap(array_copy[j], array_copy[j+1]);
			}
		}
		if(is_change == false)
			break;
	}

	auto end   = system_clock::now();
	auto duration = duration_cast<microseconds>(end - start);

	cout<<"优化版本冒泡排序后:"<<endl;
	//DisplayArray(array_copy);

	cout<<"花费了" 
     	<<double(duration.count()) * microseconds::period::num / microseconds::period::den 
     	<<"秒"<<endl;
}


void Sort::InsertSort(){
	auto array_copy = array;

	for(int i = 1; i < array_copy.size(); i++){
		int temp = array_copy[i];
		for(int j = i - 1; j >= 0; j--){
			if(temp < array_copy[j]){
				swap(array_copy[j], array_copy[j+1]);
			}else{
				break;
			}
		}
	}

	//cout<<"插入排序后:"<<endl;
	//DisplayArray(array_copy);
}


void Sort::ShellSort(){
	auto array_copy = array;

	for(int h = array_copy.size()/2; h >= 1; h = h/2){
		for(int k = 0; k < h; k++){
			for(int i = h+k; i < array_copy.size(); i+=h){
				int temp = array_copy[i];
				for(int j = i - h; j >= k; j-=h){
					if(temp < array_copy[j]){
						swap(array_copy[j], array_copy[j+h]);
					}else{
						break;
					}
				}
			}
		}
	}

	//cout<<"排序后:"<<endl;
	DisplayArray(array_copy);
}


void Sort::mergeSort(std::vector<int>& Array, int low, int height){
	if(low < height){
		mergeSort(Array, low, (low+height)/2);
		mergeSort(Array, (low+height)/2+1, height);
		Merge(Array, low, height);
	}
}

void Sort::Merge(std::vector<int>& Array, int low, int height){
	int mid = (low+height) / 2;
	int i = low, j = mid+1 , k = low;
	std::vector<int> temp(Array);

	while(i <= mid && j <= height){
		//cout<<Array[i]<<"\t"<<Array[j]<<endl;
		if(Array[i] > Array[j])
			temp[k++] = Array[j++];
		else
			temp[k++] = Array[i++];
	}
	while(i <= mid ){
		temp[k++] = Array[i++];
	}
	while(j <= height){
		temp[k++] = Array[j++];
	}
	Array = temp;
}


void Sort::MergeSort(){
	auto array_copy = array;
	mergeSort(array_copy, 0, array_copy.size()-1);
	//DisplayArray(array_copy);
}



int Sort::Partition(std::vector<int>& Array, int low, int height){
	int temp = Array[low];
	int i = low, j = height;
	while(i < j){
		while(temp <= Array[j] && i != j){
			j--;
		}
		if(j != i)
			swap(Array[i], Array[j]);
		while(Array[i] <= temp && i != j){
			i++;
		}
		if(j != i)
			swap(Array[i], Array[j]);
	}
	Array[i] = temp;
	return i;
}


void Sort::QSort(std::vector<int>& Array, int low, int height){
	if(low < height){
		int mid = Partition(Array, low, height);
		QSort(Array, low, mid - 1);
		QSort(Array, mid + 1, height);
	}
}


void Sort::QuickSort(){
	auto array_copy = array;
	QSort(array_copy, 0, array_copy.size()-1);
	DisplayArray(array_copy);
}


void Sort::HSort(std::vector<int>& Array){
	//构造大顶堆
	for(int i = Array.size()/2-1; i >= 0; i--){
		if(Array[2*i+1] > Array[i])
			swap(Array[2*i+1], Array[i]);
		if(2*i+2 < Array.size()){
			if(Array[2*i+2] > Array[i])
				swap(Array[2*i+2], Array[i]);
		}
	}

	//交换堆顶元素和末尾元素，重新调整堆
	for(int j = 0; j < Array.size()-1; j++){
		swap(Array[0], Array[Array.size()-1-j]);
		adjustHeap(Array, Array.size()-1-j);
	}
}


void Sort::adjustHeap(std::vector<int>& Array, int length){
	for(int i = length/2-1; i >= 0; i--){
		if(Array[2*i+1] > Array[i])
			swap(Array[2*i+1], Array[i]);
		if(2*i+2 < length){
			if(Array[2*i+2] > Array[i])
				swap(Array[2*i+2], Array[i]);
		}
	}
}


void Sort::HeapSort(){
	auto array_copy = array;

	HSort(array_copy);
	DisplayArray(array_copy);
}















